/* 练习：重建二叉树
 *
 * 1. 实现bitree_reconstruct()函数，根据从参数传入的前序和中序遍历结果
 *    (其中不含重复数据)，重建二叉树；
 * 2. 实现bitree_pretravel()和bitree_intravel()函数，分别用于前序和中序
 *    遍历二叉树，以验证重建的正确性。
 */
#include <stdio.h>
#include <stdlib.h>

/* 节点 */
typedef struct BiTreeNode {
	int                data;  /* 数据 */
	struct BiTreeNode* left;  /* 左子树 */
	struct BiTreeNode* right; /* 右子树 */
}	BITREE_NODE;

/* 创建节点 */
BITREE_NODE* create_node (int data) {
	BITREE_NODE* node = malloc (sizeof (BITREE_NODE));
	node->data = data;
	node->left = NULL;
	node->right = NULL;
	return node;
}

/* 销毁节点 */
void destroy_node (BITREE_NODE* node) {
	free (node);
}

/* 二叉树 */
typedef struct BiTree {
	BITREE_NODE* root; /* 树根 */
}	BITREE;

/* 创建二叉树 */
BITREE* bitree_create (void) {
	BITREE* bitree = malloc (sizeof (BITREE));
	bitree->root = NULL;
	return bitree;
}

/* 删除以参数root的目标所指向的节点为根的子树 */
void clear (BITREE_NODE** root) {
	if (*root) {
		clear (&(*root)->left);
		clear (&(*root)->right);

		destroy_node (*root);
		*root = NULL;
	}
}

/* 销毁二叉树 */
void bitree_destroy (BITREE* bitree) {
	clear (&bitree->root);
	free (bitree);
}

/* 根据前序和中序遍历结果，重建子树，返回其根节点的地址
 *
 * 前序遍历：1   2   4   7   3   5   6   8
 *           ^   ^^^^^^^^^   ^^^^^^^^^^^^^
 *           根    左子树        右子树
 *
 * 中序遍历：4   7   2   1   5   3   8   6
 *           ^^^^^^^^^   ^   ^^^^^^^^^^^^^
 *             左子树    根      右子树
 */
BITREE_NODE* reconstruct (int preorder[], int inorder[], size_t size) {
	if (! preorder || ! inorder || ! size)
		return NULL;

	BITREE_NODE* root = create_node (preorder[0]);

	size_t len; /* 左子树长度 */
	for (len = 0; len < size && inorder[len] != preorder[0]; ++len);
	if (len >= size)
		return NULL;

	root->left = reconstruct (preorder + 1, inorder, len++);
	root->right = reconstruct (preorder + len, inorder + len, size - len);

	return root;
}

/* 根据前序和中序遍历结果，重建二叉树 */
void bitree_reconstruct (BITREE* bitree, int preorder[], int inorder[],
	size_t size) {
	bitree->root = reconstruct (preorder, inorder, size);
}

/* 前序遍历以参数bitree的目标为根的子树 */
void pretravel (BITREE_NODE* root) {
	if (root) {
		printf ("%d ", root->data);
		pretravel (root->left);
		pretravel (root->right);
	}
}

/* 前序遍历 */
void bitree_pretravel (BITREE* bitree) {
	pretravel (bitree->root);
	printf ("\n");
}

/* 中序遍历以参数bitree的目标为根的子树 */
void intravel (BITREE_NODE* root) {
	if (root) {
		intravel (root->left);
		printf ("%d ", root->data);
		intravel (root->right);
	}
}

/* 中序遍历 */
void bitree_intravel (BITREE* bitree) {
	intravel (bitree->root);
	printf ("\n");
}

/* 测试用例
 *
 *     1
 *    / \
 *   2   3
 *  /   / \
 * 4   5   6
 *  \     /
 *   7   8
 */
int main (void) {
	BITREE* bitree = bitree_create ();

	int preorder[] = {1,2,4,7,3,5,6,8};
	int inorder[] = {4,7,2,1,5,3,8,6};
	size_t size = sizeof (preorder) / sizeof (preorder[0]);
	bitree_reconstruct (bitree, preorder, inorder, size);

	bitree_pretravel (bitree);
	bitree_intravel (bitree);

	bitree_destroy (bitree);
	return 0;
}
